Algorytm FCFS (First‑Come, First‑Served)

FCFS (ang. First‑Come, First‑Served) jest jednym z najprostszych algorytmów planowania procesów oraz zarządzania kolejkami. W jego najprostszej postaci kolejne żądania są obsługiwane w takiej kolejności, w jakiej pojawiły się w systemie, bez uwzględniania ich priorytetów ani czasu wykonania.

Definicja

Algorytm FCFS przyjmuje, że procesy lub żądania dyskowe są umieszczane w kolejce FIFO (ang. First‑In‑First‑Out). Pierwszy element, który wszedł do kolejki, jest również pierwszym, który z niej wychodzi.

Zasada działania

Gdy nowy proces (lub żądanie I/O) pojawia się w systemie, jest dodawany na koniec kolejki.
Jednostka przydzielająca zasoby (CPU, dysk twardy itp.) wybiera proces znajdujący się na początku kolejki.
Wybrany proces jest wykonywany do zakończenia (brak przedziałowego przydziału czasu). Po zakończeniu zostaje usunięty, a kolejny proces w kolejce przechodzi do fazy wykonywania.

Zastosowanie

Algorytm FCFS znajduje zastosowanie w:

systemach operacyjnych przy prostym planowaniu procesów w trybie jednowątkowym,
zarządzaniu dostępem do pamięci masowej (np. planowanie operacji dyskowych),
systemach kolejkowych w bankowości, transporcie publicznym lub obsłudze klientów w punktach usługowych.

Zalety

Łatwa implementacja – wymaga jedynie struktury danych typu kolejka.
Sprawiedliwość w sensie „kto pierwszy, ten pierwszy”: każdy proces otrzymuje szansę wykonania w kolejności przybycia.
Brak potrzebnych dodatkowych parametrów (priorytetów, prognozowanego czasu wykonania).

Wady

Możliwość długiego czasu oczekiwania dla krótkich procesów, gdy przed nimi znajduje się długi proces – zjawisko znane jako konwulsja (ang. convoy effect).
Nieefektywne wykorzystanie zasobów w środowiskach o zróżnicowanym czasie trwania zadań.
Brak adaptacji do zmian obciążenia systemu – algorytm nie bierze pod uwagę bieżącego stanu systemu.

Porównanie z innymi algorytmami planowania

Algorytm	Typ kolejki	Sprawiedliwość	Średni czas oczekiwania	Złożoność implementacji
FCFS	FIFO	Wysoka	Wysoki (zależny od długości pierwszych zadań)	Najniższa
SJF (Shortest Job First)	Priorytetowa (czas trwania)	Średnia	Niski	Średnia
RR (Round‑Robin)	Cykliczna (kwant czasu)	Wysoka	Średni	Średnia
Priority Scheduling	Priorytetowa	Niska (może dochodzić do głodzenia)	Zmienny	Średnia‑wysoka

Przykładowa implementacja (pseudokod)

queue<Process> FCFSQueue;

function addProcess(Process p):
    FCFSQueue.enqueue(p)

function schedule():
    while not FCFSQueue.isEmpty():
        current = FCFSQueue.dequeue()
        execute(current)   // wykonaj proces do zakończenia
        // po zakończeniu przejdź do następnego elementu kolejki

Historia

Pierwsze zastosowania koncepcji FIFO w systemach operacyjnych sięgają lat 1960, kiedy to wprowadzono je jako podstawowy mechanizm przydzielania czasu procesora w wczesnych systemach operacyjnych typu batch. W literaturze klasycznej, np. w książce Operating System Concepts autorstwa Abrahama Silberschatz, algorytm FCFS jest prezentowany jako punkt wyjścia do omawiania bardziej złożonych strategii planowania.

Przykład praktyczny

Załóżmy, że kolejka procesów zawiera cztery zadania o czasach wykonywania: 8 s, 4 s, 2 s oraz 1 s. Algorytm FCFS obsłuży je w tej kolejności, co spowoduje następujące czasy zakończenia:

Proces 1 – zakończenie po 8 s
Proces 2 – zakończenie po 12 s (8 s + 4 s)
Proces 3 – zakończenie po 14 s (12 s + 2 s)
Proces 4 – zakończenie po 15 s (14 s + 1 s)

Średni czas oczekiwania wynosi (0 + 8 + 12 + 14) / 4 = 8,5 s, co jest relatywnie wysokim wynikiem w porównaniu do algorytmów krótszych zadań (np. SJF).

Literatura

Silberschatz, A., Galvin, P. B., & Gagne, G. – Operating System Concepts, 10th ed., Wiley, 2018.
Stallings, W. – Operating Systems: Internals and Design Principles, 9th ed., Pearson, 2015.
Tanenbaum, A. S. – Modern Operating Systems, 4th ed., Prentice Hall, 2014.

Algorytm FCFS, choć prosty i łatwy do implementacji, zazwyczaj nie spełnia wymagań współczesnych systemów operacyjnych pod względem efektywności i responsywności. W praktyce jest stosowany głównie jako komponent bardziej złożonych strategii lub w środowiskach, w których priorytety i czas odpowiedzi nie odgrywają kluczowej roli.